package com.tlvip.arithmetic.ch10;

import java.util.concurrent.LinkedBlockingQueue;

/**
 * <p>description：二叉树</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/31/21</p>
 * Author mac
 *
 * @version 1.0
 */

class MyTreeNode {
    String value;
    MyTreeNode left;
    MyTreeNode right;

    public MyTreeNode(String value, MyTreeNode left, MyTreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public MyTreeNode getLeft() {
        return left;
    }

    public void setLeft(MyTreeNode left) {
        this.left = left;
    }

    public MyTreeNode getRight() {
        return right;
    }

    public void setRight(MyTreeNode right) {
        this.right = right;
    }
}

public class BinaryTree {

    public static void main(String[] args) {
        // 先初始化叶子节点
        MyTreeNode D = new MyTreeNode("D", null, null);
        MyTreeNode H = new MyTreeNode("H", null, null);
        MyTreeNode K = new MyTreeNode("K", null, null);

        MyTreeNode C = new MyTreeNode("C", D, null);
        MyTreeNode G = new MyTreeNode("G", H, K);

        MyTreeNode B = new MyTreeNode("B", null, C);
        MyTreeNode F = new MyTreeNode("F", G, null);
        MyTreeNode E = new MyTreeNode("E", null, F);

        MyTreeNode A = new MyTreeNode("A", B, E);
        System.out.println("前序遍历：");
        pre(A);
        System.out.println();
        System.out.println("中序遍历：");
        mid(A);
        System.out.println();
        System.out.println("后续遍历：");
        post(A);
        System.out.println("层次遍历：");
        level(A);
    }

    public static void print(MyTreeNode myTreeNode) {
        if (null != myTreeNode) {
            System.out.print(myTreeNode.getValue() + "   ");
        }
    }

    /**
     * 前序遍历：根左右
     * 每个点需要访问2次
     * 时间复杂度:O(n)
     *
     * @param myTreeNode
     */
    public static void pre(MyTreeNode myTreeNode) {
        print(myTreeNode);
        if (myTreeNode.left != null) {
            pre(myTreeNode.left);
        }
        if (myTreeNode.right != null) {
            pre(myTreeNode.right);
        }
    }

    /**
     * 中序遍历：左根右
     *
     * @param myTreeNode
     */
    public static void mid(MyTreeNode myTreeNode) {
        if (myTreeNode.left != null) {
            mid(myTreeNode.left);
        }
        print(myTreeNode);
        if (myTreeNode.right != null) {
            mid(myTreeNode.right);
        }
    }

    /**
     * 后续遍历：左右根
     *
     * @param myTreeNode
     */
    public static void post(MyTreeNode myTreeNode) {
        if (myTreeNode.left != null) {
            post(myTreeNode.left);
        }

        if (myTreeNode.right != null) {
            post(myTreeNode.right);
        }
        print(myTreeNode);
    }

    public static void level(MyTreeNode myTreeNode) {
        LinkedBlockingQueue<MyTreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(myTreeNode);
        LinkedBlockingQueue<MyTreeNode> queueNew;
        do {
            queueNew = new LinkedBlockingQueue<>();
            System.out.println();
            while (!queue.isEmpty()) {
                MyTreeNode myTreeNode1 = queue.poll();
                print(myTreeNode1);
                if (null != myTreeNode1.getLeft()) {
                    queueNew.offer(myTreeNode1.getLeft());
                }
                if (null != myTreeNode1.getRight()) {
                    queueNew.offer(myTreeNode1.getRight());
                }
            }
            System.out.println();
            queue = queueNew;
        } while (!queueNew.isEmpty());

    }
}
